package org.example.algorithm;

import org.example.path.Path;
import org.example.treasure.Treasure;

import java.util.ArrayList;

public class BestLifePath {
    //生成最佳生命路径的算法


    public BestLifePath(ArrayList<Treasure> graph,Treasure source) {
        ArrayList<Treasure> list = new ArrayList<>(graph);
        source.dist = 0;

        while (!list.isEmpty()){
            //2.找到最短路径的点
            Treasure cur = chooseMinDistVertex(list);
            //3.跟新附近的所有节点
            updateDist(cur,graph);
            //4.删除现在的节点
            list.remove(cur);
            cur.isVisible = true;
        }


        for (Treasure treasure : graph) {
            treasure.isVisible = false;
        }

//        for (Treasure vertex : graph) {
//            System.out.println(vertex.name +" 长度："+ vertex.dist + "   路径" + vertex.route.toString());
//        }
    }
    /**
     * 选择并更新最小点
     * @param list
     * @return
     */
    private static Treasure chooseMinDistVertex(ArrayList<Treasure> list) {
        Treasure treasure = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            Treasure current = list.get(i);
            if (current.dist < treasure.dist){
                treasure = current;
            }
        }

        return treasure;
    }


    private static void updateDist(Treasure cur,ArrayList<Treasure> graph) {
        for (Path edge : cur.getPaths()) {
            int dist = cur.dist + edge.damage;
            Treasure treasure = getTreasure(edge.to,graph);
            if (!treasure.isVisible){
                if (dist < treasure.dist){
                    treasure.dist = dist;
                    //更新路径
                    treasure.route = new ArrayList<>(cur.route);
                    treasure.route.add(cur);
                }
            }
        }
    }

    /**
     * 返回目的地部落
     * @param to
     * @param graph
     * @return
     */
    private static Treasure getTreasure(String to,ArrayList<Treasure> graph){
        int index = to.charAt(0) - 'A';
        Treasure treasure =  graph.get(index);
        return treasure;
    }
}
